For the purpose of explanation, and to highlight a particular application of the invention, a computer system including a display device for which the image is resolved into a two dimensional array of picture elements (pixels) will be described. Each pixel can therefore be represented by a bit stored in a bit map arranged within a memory which is part of the display system. A display system can be a computer system itself, or an optional, peripheral adapter, such as a display adapter card installed in a computer system.
For simplicity of explanation, a process by which bits are either set or not set in order to define a boundary or area in a display memory is referred to as a drawing process.
A display system is commonly utilised to fill areas of a displayed image, such as slices of a pie chart for instance, with a particular color or shading pattern. This is commonly achieved by means of a boundary defined area fill process.
In order to correctly fill an area, area boundary segments should be drawn according to a set of general rules which can be summarized as follows:
a) A new area boundary pixel status is determined according to an Exclusive-OR function by which a new boundary pixel is combined with a current boundary pixel.
b) If an area boundary segment has a positive gradient, the second pixel in the segment is not set. Similarly, if an area boundary segment has a negative gradient, the first pixel in the segment is not set.
c) If an area boundary segment has a shallow gradient, and is therefore composed of horizontal runs of adjacent pixels, the first pixel of the segment only is set if the gradient is positive and the last pixel of the segment only is set if the gradient is negative.
d) If an area boundary segment is horizontal, the pixels composing the segment are not set. An area boundary segment specified by a single pixel is rejected in a similar fashion.
Failure to adhere to such rules causes an area filling procedure to start or stop unpredictably or in incorrect locations within the destination bit map.
EP-A-0145821 describes an area boundary drawing procedure implemented by a combination of hardware and software, and the area fill procedure is implemented by hardware. More specifically, it describes an area filling procedure for a graphics displaying computer system in which, in order to draw filled areas, additional control logic is supplied to define an outline of the area in an auxiliary memory using Bresenham's Algorithm. Area filling logic consisting of Exclusive-OR gates is used to fill the enclosed area in the refresh buffer as the enclosing outline is read from the auxiliary memory. A combination of hardware and software is used to examine each line segment and either reject it according to conventional rules or define it with the appropriate Y direction, swapping end points if necessary.
Such a process is suitable for drawing an area boundary specified by a succession of single line segments. However, problems arise when the area boundary includes complex curves. In such cases, it is not necessarily possible to simply swap end points to ensure a consistent drawing direction, since a general curve may have some sections moving up the image while other sections are moving down.